package LeetCode;

import java.util.Stack;

public class MaximalRectangle
{
  //should pass both
  public static int maximalRectangle(char[][] matrix)
  {
    // Start typing your Java solution below
    // DO NOT write main() function
    int m = matrix.length;
    if (m == 0) return 0;
    int n = matrix[0].length;
    if (n == 0) return 0;
    int maxrec = 0;
    int[] height = new int[n];
    for (int i = 0 ; i < m ; i++) {

      for (int j = 0 ; j < n ; j++) {
        if (matrix[i][j] == '1')
          height[j]++;
        else
          height[j] = 0;
      }
      int tmp = largestRectangleArea(height);
      if (maxrec < tmp) maxrec = tmp;
    }
    return maxrec;

  }

  
  //this is the same method of largest rectangle in histogram
  public static int largestRectangleArea(int[] height)
  {
    Stack<Integer> heights = new Stack<Integer>();
    Stack<Integer> indexes = new Stack<Integer>();
    int largestsize = 0;
    for (int i = 0 ; i < height.length ; i++) {
      if (heights.isEmpty() || height[i] > heights.peek()) {
        heights.push(height[i]);
        indexes.push(i);
      }
      else if (height[i] < heights.peek()) {
        int lastindex = 0;

        while (!heights.isEmpty() && height[i] < heights.peek()) {
          lastindex = indexes.pop();
          int tempsize = heights.pop() * (i - lastindex);
          if (tempsize > largestsize) {
            largestsize = tempsize;
          }
        }

        heights.push(height[i]);
        indexes.push(lastindex);
      }
    }

    while (!heights.isEmpty()) {
      int tempsize = heights.pop() * (height.length - indexes.pop());
      if (tempsize > largestsize) {
        largestsize = tempsize;
      }
    }

    return largestsize;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
  }

}
